package Demo7;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> row = new ArrayList();
        //1、排序
        Arrays.sort(nums);
        //2、固定一个数i
        int i = 0;
        while(i < nums.length){

            if(nums[i] > 0){
                break;
            }
            int left = i+1;
            int right = nums.length - 1;
            while(left < right){
                //3、在该数后面的区间内，利用“双指针算法”，快速找到两个数的和等于-a即可
                if(nums[right]+nums[left] > -nums[i]){
                    right--;
                }else if(nums[right]+nums[left] < -nums[i]){
                    left++;
                } else{
                    List<Integer> col = new ArrayList();
                    col.add(nums[i]);
                    col.add(nums[left]);
                    col.add(nums[right]);
                    row.add(col);
                    //缩小区间继续寻找
                    left++;
                    right--;
                    //对nums[left]和nums[right]查重+避免越界
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]){
                        right--;
                    }
                }
            }
            i++;
            //i去重+避免越界
            while(i < nums.length && nums[i] == nums[i-1]){
                i++;
            }
        }
        return row;
    }
}
